package 字符串;

public class reorganizeString {
    public String reorganizeString(String s) {
        int n=s.length();
        int[] count = new int[26];
        int maxCount=0;
//        统计每个字符出现的频次
        for (int i=0;i<n;++i){
            char c = s.charAt(i);
            count[c-'a']++;
//            找到频次出现最高的那个字符
            maxCount=Math.max(maxCount,count[c-'a']);
        }
        if(maxCount>(n+1)/2) return "";
        int oddIndex=1,evenIndex=0;
        char[] ans = new char[n];
        for (int i=0;i<26;++i){
            char c=(char) ('a'+i);
            while (count[i]>0 && count[i]<=n/2 && oddIndex<n){
                ans[oddIndex]=c;
                count[i]--;
                oddIndex+=2;
            }
            while (count[i]>0){
                ans[evenIndex]=c;
                count[i]--;
                evenIndex+=2;
            }
        }
        return String.valueOf(ans);

    }
}
